package com.zhaoyue.study.algorithm;

/**
 * Created with IntelliJ IDEA.
 * User: Administrator
 * Date: 2017/1/20
 * Time: 11:35
 * 动态规划法 算法
 * 基本概念：每次决策依赖当前状态 又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，
 * 所以这种多阶段最优化决策过程就是动态规划
 *
 * 基本与分治法类型，就是将待求的解问题分为若干个子问题，按顺序求解子阶段,前一子问题的解对后一个子问题提供了有用的信息
 * 子问题之前不是相互独立的
 *
 */
public class DynamicPlan {


    public int countWays(int[] penny, int n, int aim) {

        //如果条件不满足返回0
        if (n == 0 || penny == null || aim < 0) {
            return 0;
        }

        int[][] pd = new int[n][aim + 1];
        for (int i = 0; i < n; i++) {
            pd[i][0] = 1;
        }
        for (int i = 1; penny[0] * i <= aim; i++) {
            pd[0][penny[0] * i] = 1;
        }

//        for(){
//            for(){
//
//            }
//        }
        return 0;

    }



    public static void main(String[] args) {

    }

}
